package com.cuz.hot100;

public class Q72minDistance {
    public static void main(String[] args) {
        String target = "opasdaa";
        String source = "executioasdan";
        System.out.println(minDistance2(target, source));
        System.out.println(minDistance1(target, source));
    }

    public static int minDistance2(String target, String source) {
        if (target == null) {
            target = "";
        }
        if (source == null) {
            source = "";
        }
        if (target.length() == 0) {
            return source.length();
        }
        if (source.length() == 0) {
            return target.length();
        }
        int tLen = target.length();
        int sLen = source.length();
        //dp[t][s] 表示 target[0---t-1] source[0..s-1] 字符匹配的 代价
        int[][] dp = new int[tLen + 1][sLen + 1];
        for (int i = 0; i <= tLen; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= sLen; i++) {
            dp[0][i] = i;
        }
        for (int t = 1; t < tLen + 1; t++) {
            for (int s = 1; s < sLen + 1; s++) {
                //前面相同的代价 + 如果字符相同 那么+0 or +1
                int update = dp[t - 1][s - 1] +
                        (source.charAt(s - 1) == target.charAt(t - 1) ? 0 : 1);
                //删除
                int delete = dp[t][s - 1] + 1;
                //新增
                int add = dp[t - 1][s] + 1;
                dp[t][s] = Math.min(Math.min(update, delete), add);
            }
        }
        return dp[tLen][sLen];
    }

    public static int minDistance1(String word1, String word2) {
        if (word1 == null) {
            word1 = "";
        }
        if (word2 == null) {
            word2 = "";
        }
        if (word1.length() == 0) {
            return word2.length();
        }
        if (word2.length() == 0) {
            return word1.length();
        }
        int len1 = word1.length();
        int len2 = word2.length();
        return process(word1.toCharArray(), word2.toCharArray(),
                len1, len2);
    }

    //将 source[0...indexS] 编辑成 target[0...indexT]需要的花费
    private static int process(char[] target, char[] source, int indexT, int indexS) {
        if (indexS == 0) {
            return indexT;
        }
        if (indexT == 0) {
            return indexS;
        }
        int ans;
        //更新 字符相同 那么不需要加1
        ans = process(target, source, indexT - 1, indexS - 1)
                + (source[indexS - 1] == target[indexT - 1] ? 0 : 1);
        //新增
        ans = Math.min(ans, process(target, source, indexT - 1, indexS) + 1);
        //删除
        ans = Math.min(ans, process(target, source, indexT, indexS - 1) + 1);
        return ans;
    }

}
